class Solution {
public:

    vector<vector<int>> g;
    vector<int> d1, d2, p1, up;

    void dfs1(int u, int father) {

        d1[u] = d2[u] = 0;
        for(int j: g[u]) {

            if(j == father) continue;
            dfs1(j, u);

            int d = d1[j] + 1;
            if(d >= d1[u]) {
                d2[u] = d1[u];
                d1[u] = d;
                p1[u] = j;
            }else if (d >= d2[u]){
                d2[u] = d;
            }
        }
    }

    void dfs2(int u, int father){
        for(int j: g[u]) {
            if(j == father) continue;
            if(j == p1[u]) {
                up[j] = max(up[u], d2[u]) + 1;
            }else{
                up[j] = max(up[u], d1[u]) + 1;
            }
            dfs2(j, u);
        }
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {

        g.resize(n);
        d1 = d2 = p1 = up = vector<int>(n);

        for (auto &e: edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }
        vector<int> res;
        dfs1(0, -1);
        dfs2(0, -1);

        int min_heigh = n + 1;
        for(int i = 0; i < n; ++i){

            min_heigh = min(min_heigh, max(d1[i], up[i]));
        }
        for(int i = 0; i < n; ++i){

            if(max(d1[i], up[i]) == min_heigh) res.push_back(i);
        }

        return res;
    }
};
